import java.util.Arrays;

/**
 * @author Wang Chen Peng
 * @date 2019/01/10
 * describe:移动0
 * https://leetcode-cn.com/problems/move-zeroes/
 */
public class MoveZeroes {

    /**
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * <p>
     * 示例:
     * <p>
     * 输入: [0,1,0,3,12]
     * 输出: [1,3,12,0,0]
     * 说明:
     * <p>
     * 必须在原数组上操作，不能拷贝额外的数组。
     * 尽量减少操作次数。
     */
    public static void main(String[] args) {

        int[] arg = new int[]{0, 1, 0, -1, 9};
        moveZeroes(arg);
    }

    /**
     * 通过 平均超过10%
     */
    static void moveZeroes(int[] nums) {

        for (int xIndex = 0; xIndex < nums.length; xIndex++) {
            int yIndex = xIndex + 1;
            if (nums[xIndex] == 0&&yIndex<nums.length) {

                if (nums[yIndex] != 0) {
                    int temp = nums[xIndex];
                    nums[xIndex] = nums[yIndex];
                    nums[yIndex] = temp;
                }else{
                    while(yIndex<nums.length){
                        if (nums[yIndex] != 0){
                            int temp = nums[xIndex];
                            nums[xIndex] = nums[yIndex];
                            nums[yIndex] = temp;
                            break;
                        }
                        yIndex++;
                    }
                }
            }
        }

        System.out.println(Arrays.toString(nums));
    }

    /**
     * 明虎
     */
    public static void bac(int[] as) {
        int k = -1;
        for (int i = 0; i < as.length; i++) {
            if (as[i] == 0 && k < 0) {
                k = i;
            }
            if (as[i] != 0 && k >= 0) {
                as[k] = as[i];
                as[i] = 0;
                k++;
            }
        }
        System.out.println(Arrays.toString(as));
    }

    /**
     * 官方最佳实践
     */
    static void moveZeroes1(int[] nums) {
        int aa = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                aa++;
            } else {
                nums[i - aa] = nums[i];
            }

        }
        for (int i = nums.length - aa; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

    /**
     * 官方第二实践
     */
    static void moveZeroes2(int[] nums) {
        int i = 0;
        int start = 0;
        while(i<nums.length){
            if(nums[i]!=0){
                nums[start] = nums[i];
                if(start != i){
                    nums[i]=0;
                }
                start++;
            }
            i++;
        }
    }
}
